/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/5/11
 * \* Time: 20:11
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 反转链表 {
    public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
    }

    /**
     * 递归解法
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode last=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return last;
    }

    /**
     * 双指针迭代法
     * @param head
     * @return
     */
    public ListNode ReverseList(ListNode head){
        ListNode cur=head,pre=null;
        while (cur!=null){
            ListNode tmp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=tmp;
        }
        return pre;
    }
}